16. 最接近的三数之和

Similar Question

leading to the advanced question

Solution Tips

方案一: 排序 + 对撞指针

var threeSumClosest = function (nums, target) {
    let res = Number.MAX_SAFE_INTEGER;
    const len = nums.length;
    nums.sort((a, b) => a - b);
    // 因为输入只有一个解, 所以按理来说是不存在重复的数的, 但是跳过重复的逻辑保留也无法大碍

    for (let i = 0; i < len - 2; i++) {
        // 需要和上一次枚举的数不相同
        if (nums[i] == nums[i - 1]) {
            continue;
        }
        // 双指针
        let left = i + 1;
        let right = len - 1;
        // 指针对撞式结束循环
        while (left < right) {

            let sum = nums[i] + nums[left] + nums[right];

            // 直接相等了, 直接退出就好
            if (sum === target) return sum;

            if (Math.abs(target - sum) < Math.abs(target - res)) {
                res = sum
            }

            if (sum < target) {
                // left太小了，left指针右移
                // 取等于，因为符合条件之后也需要移动指针
                while (left < right && nums[left] === nums[++left]); // 如果相等就跳过
            }
            if (sum > target) {
                // right太大了，right指针左移
                while (left < right && nums[right] === nums[--right]); // 如果相等就跳过
            }
        }
    }

    return res;
};

let nums = [0, 1, 2], target = 3
console.log(threeSumClosest(nums, target));